1. Field of the Invention
This invention relates to a method for encoding a signal. This invention particularly relates to a signal encoding method, wherein a signal is compressed with variable code length encoding.
2. Description of the Prior Art
Image signals representing continuous tone images, such as television signals, are composed of enormous amounts of information, and a broad-band transmission line is required for transmission of the image signals. Such image signals involve much redundancy, and various attempts have been made to compress the image signals by restricting the redundancy. Also, in recent years, recording of continuous tone images on optical disks, magnetic disks, or the like, has been generally put into practice. In such cases, image signal compression is generally carried out for the purpose of efficiently recording the image signals on a recording medium.
As one of the methods for compressing an image signal, a compressing processing method utilizing prediction encoding has heretofore been employed. Specifically, in cases where an image signal is to be stored or transmitted, the image signal is subjected to compression processing based on prediction encoding, and the amount of the image signal is thereby reduced. The compressed image signal is then stored or transmitted. When the image which is represented by the image signal is to be reproduced, the compressed image signal is subjected to decoding processing and is thereby decompressed. Thereafter, a visible image is reproduced from the decompressed image signal.
Also, as one of the methods for compressing an image signal, a method utilizing vector quantization has heretofore been used. The method comprises the steps of (i) dividing a two-dimensional image signal into blocks, each of which comprises the image signal components representing an arbitrary number K of picture elements adjacent to one another in the image, (ii) selecting a vector, which corresponds with the minimum distortion to the set of the image signal components in each of the blocks, from a code book composed of a plurality of vectors, which are different from one another and prepared in advance by defining K number of vector elements, and (iii) encoding the information, which represents the selected vector, in association with the block.
Since the image signal components in the block as described above have high correlation to one another, the image signal components in each block can be represented very accurately by one of a comparatively small number of vectors prepared in advance. Therefore, instead of the actual image signal being transmitted or recorded, transmission or recording of the image signal can be carried out by transmitting or recording the codes representing the vectors. In this manner, signal compression can be achieved. By way of example, the amount of the image signal components, which represent 64 picture elements in a continuous tone image having 256 levels (=8 bits) of density scale, is equal to 512 bits (=8.times.64). In such cases, the image signal components representing the 64 picture elements may be grouped as a single block, and the image signal components in the block may be represented by a vector, which is composed of 64 vector elements. Also, a code book including 256 such vectors may be prepared. In such cases, the amount of the information per block becomes equal to the amount of the information required to discriminate between the vectors, i.e. 8 bits. Consequently, in such cases, the amount of the signal can be compressed to 8/(8.times.64)=1/64.
The image signal is compressed in the manner described above, and the compressed image signal is recorded or transmitted. Thereafter, the vector elements of each of the vectors, which are represented by the vector discriminating information, are taken as reconstructing information for each of the blocks, and the original image is reproduced by using the reconstructing information.
One approach to improvement of the compressibility in the image signal compression by prediction encoding is to decrease the bit resolution (density resolution) of the image signal, i.e. to carry out quantization processing for quantizing the image signal more coarsely, in addition to prediction encoding processing.
Therefore, in U.S. Pat. No. 4,776,029, the applicant proposed a method for encoding a signal with interpolation encoding, wherein the prediction encoding technique and the quantization technique are combined with each other. With the proposed method, image signal components of an image signal are classified into main components, which have been sampled at appropriate sampling intervals, and interpolated components other than the main components. The interpolated components are then subjected to interpolation prediction encoding processing based on the main components, i.e. the values of the interpolated components are predicted with the interpolation prediction from the main components. Thereafter, prediction errors between the predicted values and the actual values of the interpolated components are encoded into variable length codes, such as Huffman codes (i.e. are converted into codes, the lengths of which vary for different values of the prediction errors). In this manner, the image signal is encoded.
With the Huffman encoding, for example, the occurrence probability of a certain signal is calculated. In accordance with the frequency of occurrence of each signal value, a short code is allocated to a signal value which occurs more frequently, and a long code is allocated to a signal value which occurs less frequently. In this manner, the amount of code for the entire signal is kept small.
During the compression of an image signal, the image signal compressibility should be as high as possible. However, it is technically difficult to increase the compressibility markedly during the interpolation encoding. Therefore, in order for a high compressibility to be achieved, it is considered that component number decreasing processing, which results in a coarse spatial resolution, and the interpolation encoding be combined with each other.
Therefore, in U.S. Pat. No. 5,086,489, the applicant proposed a method for compressing an image signal, wherein the interpolation encoding and the component number decreasing processing are combined with each other, and wherein a high compressibility is achieved while good image quality is being kept.
As methods for processing image signals, the so-called "multi-resolution transform methods" have heretofore been proposed. With the proposed multi-resolution transform methods, an image is transformed into multi-resolution images, each of which is of one of a plurality of different frequency bands. Each of the multi-resolution images of the different frequency bands is subjected to predetermined processing and is then subjected to inverse multi-resolution transform. In this manner, an ultimate processed image is obtained. As the technique for transforming the image into the multi-resolution images, a wavelet transform, a Laplacian pyramid technique, a Fourier transform, or the like, is employed.
How the wavelet transform is carried out will be described hereinbelow.
The wavelet transform has recently been developed as a frequency analysis method and has heretofore been applied to stereo pattern matching, signal compression, and the like. The wavelet transform is described in, for example, "Wavelets and Signal Processing," by Olivier Rioul and Martin Vetterli, IEEE SP Magazine, pp. 14-38, October 1991; and "Zero-Crossings of a Wavelet Transform," by Stephane Mallat, IEEE Transactions on Information Theory, Vol. 37, No. 4, pp. 1019-1033, July 1991.
With the wavelet transform, a signal is transformed into frequency signals, each being of one of a plurality of different frequency bands, by utilizing a function h, which is shown in FIG. 9, as a basic function and in accordance with the formula ##EQU1## wherein f(t): the signal having an arbitrary wave form,
W(a,b): the wavelet transform of f(t), ##EQU2## a: the degree of contraction of the function, b: the amount of movement in the horizontal axis direction. PA1 i) quantizing the signal, a quantized signal being thereby obtained, PA1 ii) separating the quantized signal into a binary signal, which represents whether the signal values of the quantized signal are equal to zero or are other than zero, and a sign and intensity signal, which is constituted of a sign and intensity with respect to signal components of the quantized signal having signal values other than zero, PA1 iii) converting the binary signal such that the information of the binary signal, which represents N picture elements, may be converted into a signal, which represents a single picture element and is composed of N bits, a converted binary signal being thereby obtained, and PA1 iv) encoding the converted binary signal and the sign and intensity signal.
Therefore, the problems with regard to a false oscillation, which occurs with Fourier transform, do not occur. Specifically, when filtering processing is carried out by changing the period and the degree of contraction of the function h and moving the function h on an original signal, frequency signals, each of which is adapted to one of desired frequencies ranging from a fine frequency to a coarse frequency. By way of example, FIG. 10 shows signals, which are obtained by carrying out the wavelet transform on an original signal Sorg and then carrying out inverse wavelet transform for each of frequency bands. FIG. 11 shows signals, which are obtained by carrying out Fourier transform on the original signal Sorg and then carrying out inverse Fourier transform for each of the frequency bands. As will be understood from FIGS. 10 and 11, the wavelet transform has the advantage over the Fourier transform in that a frequency signal of a frequency band corresponding to the oscillation of the original signal Sorg can be obtained. Specifically, with the Fourier transform, an oscillation occurs in a part B' of a frequency band h, which corresponds to a part B of the original signal Sorg. However, with the wavelet transform, as in the original signal Sorg, no oscillation occurs in a part A' of a frequency band hh, which corresponds to a part A of the original signal Sorg.
Also, a method for compressing an image signal by utilizing the wavelet transform has been proposed in, for example, "Image Coding Using Wavelet Transform" by Marc Antonini, et al., IEEE Transactions on Image Processing, Vol. 1, No. 2, pp. 205-220, April 1992.
With the proposed method, wavelet transform is carried out on an original image signal representing an image, and the original image signal is thereby transformed into image signals, each being of one of a plurality of different frequency bands. Thereafter, vector quantization is carried out on each of the image signals such that a small number of bits per picture element may be allocated to an image signal of a high frequency band, which image signal carries much noise, and a large number of bits per picture element may be allocated to an image signal of a low frequency band, which image signal carries the information representing the major object. In this manner, the original image signal is compressed. With the proposed method, the compressibility of the original image signal can be kept high. Also, the original image can be restored perfectly by carrying out inverse wavelet transform on the compressed image signal.
The Laplacian pyramid technique is proposed in, for example, U.S. Pat. No. 5,467,404 and EP 610604 A1. With the proposed Laplacian pyramid technique, mask processing is carried out on the original image by using a mask having characteristics such that it may be approximately represented by a Gaussian function. A sub-sampling operation is then carried out on the resulting image in order to thin out the number of the picture elements to one half along each of two-dimensional directions of the array of the picture elements in the image, and an unsharp image having a size of one-fourth of the size of the original image is thereby obtained. Thereafter, a picture element having a value of 0 is inserted into each of the points on the unsharp image, which were eliminated during the sampling operation, and the image size is thereby restored to the original size. Mask processing is then carried on the thus obtained image by using the aforesaid mask, and an unsharp image is thereby obtained. The thus obtained unsharp image is subtracted from the original image, and a detail image of a predetermined frequency band of the original image is thereby obtained. This processing is iterated with respect to the obtained unsharp image, and an arbitary number N of unsharp images having sizes of 1/2.sup.2N of the size of the original image are thereby formed. As described above, the sampling operation is carried out on the image, which has been obtained from the mask processing with the mask having characteristics such that it may be approximately represented by the Gaussian function. Therefore, though the Gaussian filter is used actually, the same processed image as that obtained when a Laplacian filter is used is obtained. Also, in this manner, the images of low frequency bands, which have the sizes of 1/2.sup.2N of the size of the original image are successively obtained from the image of the original image size. Therefore, the group of the images obtained as a result of the processing is referred to as the Laplacian pyramid.
The Laplacian pyramid technique is described in detail in, for example, "Fast Filter Transforms for Image Processing" by Burt P. J., Computer Graphics and Image Processing, Vol. 16, pp. 20-51, 1981; "Fast Computation of the Difference of Low-Pass Transform" by Growley J. L., Stern R. M., IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 6, No. 2, March 1984; "A Theory for Multiresolution Signal Decomposition; The Wavelet Representation" by Mallat S. G., IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 11, No. 7, July 1989; "Image Compression by Gabor Expansion" by Ebrahimi T., Kunt M., Optical Engineering, Vol. 30, No. 7, pp. 873-880, July 1991; and "Multiscale Image Contrast Amplification" by Pieter Vuylsteke, Emile Schoeters, SPIE, Vol. 2167, Image Processing (1994), pp. 551-560.
However, with the aforesaid methods for compressing an image signal by utilizing the multi-resolution transform, it is necessary for the image signal to be compressed by vector quantization. Therefore, if the compressibility is increased even further, there will be the risk that the image quality of the original image is lost. Thus there is a limit in the increase in the compressibility of the image signal. Also, in cases where an image signal is quantized, if the number of bits per picture element is set at a large value during the quantization of the image signal, the compressibility of the image signal will become low, but a compressed image signal can be obtained which represents an image close to the original image. Therefore, in such cases, the image quality of the image reconstructed from the compressed image signal can be kept good. If the number of bits per picture element is set at a small value, a large error will occur in restoring the original image signal from the compressed image signal. Such an error appears as noise in the restored image. Therefore, in such cases, the image quality of the image reconstructed from the compressed image signal becomes bad. However, in such cases, the lengths of the codes become short during the encoding, and therefore the signal compressibility can be kept high.
Therefore, the applicant proposed a novel method for compressing an image signal in U.S. Ser. No. 08/253,857. With the proposed method for compressing an image signal, wavelet transform is carried out on the original image signal, and the original image signal is thereby decomposed into the image signals, each being of one of a plurality of different frequency bands. The degree of importance of each of different portions of the image is determined from one of the image signals, and labeling processing is carried out on the image in accordance with the determined degree of importance of each of different portions of the image. In accordance with the results of the labeling processing, the image signals are quantized such that a larger number of bits may be allocated to each of picture elements in a portion of the image determined as having a higher degree of importance, and such that a smaller number of bits may be allocated to each of picture elements in a portion of the image determined as having a low degree of importance. Accordingly, with the proposed method for compressing an image signal, as for an important portion of the image, the image signals can be compressed such that the image quality may be kept good. As for an image portion which is not important, the image signals can be compressed with a high compressibility. As a result, the compressibility of the image signals can be kept high such that the image quality of the important portion of the image may not become bad.
However, in the various methods for compressing signals described above, the problems are encountered in that, in cases where the quantized signal is encoded with the Huffman encoding, or the like, as the amount of information to be encoded (entropy) becomes small, the encoding efficiency becomes low. Specifically, in the Huffman encoding, it is necessary that 1 bit per picture element be allocated to the quantized signal, and therefore the mean code length cannot be set to be less than 1. As a result, even if the amount of information of the quantized signal (entropy) is equal to approximately 1 or less than 1, the encoded signal will always have 1 bit, and therefore the encoding efficiency (=entropy/mean code length) cannot be kept high.